package lc.q101_150;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Q140 {

    public List<String> wordBreak(String s, List<String> wordDict) {
        // 首先dp判断在某处是否存在解
        boolean[] dp = new boolean[s.length() + 1];
        // dp表示在某处能否拆分
        // 那么就有表达式dp[i] = true if 存在j < i 使得 wordDict 包含s(j,i)并且dp[j]是true
        dp[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (dp[j] && wordDict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    break;
                }
            }
        }
        List<String> res = new ArrayList<>();
        if (dp[s.length()]) {
            dfs(s, wordDict, dp, s.length(), res, new LinkedList<>());
        }
        return res;
    }

    private void dfs(String s, List<String> wordDict, boolean[] dp, int len, List<String> res, Deque<String> split) {
        if (len == 0) {
            // 到最后了
            res.add(String.join(" ", split));
            return;
        }
        // 从后往前找
        for (int length = len - 1; length >= 0; length--) {
            if (dp[length] && wordDict.contains(s.substring(length, len))) {
                split.addFirst(s.substring(length, len));
                dfs(s, wordDict, dp,length , res, split);
                split.removeFirst();
            }
        }
    }

}
